#include<iostream>

using namespace std;

struct ListNode{
    int value;
    ListNode * next;
};

ListNode * createNode(int * data, int length){
    if ( data == nullptr || length <= 0 )
        return nullptr;
    ListNode * head = new ListNode();
    head -> value = data[0];
    head -> next = nullptr;
    ListNode * pHead = head;
    for ( int i=1;i<length; i++ ){
        ListNode * node = new ListNode();
        node -> value = data[i];
        node -> next = nullptr;
        pHead = pHead -> next = node;
    }
    return head;
}

// 通过一次遍历找到倒数第k个元素的节点
ListNode * findEndOfNode1(ListNode * head, int index ){
    if ( head == nullptr )
        return nullptr;
    int front = 0;
    int tail = 0;
    ListNode * tailNode = head;
    ListNode * frontNode = head;
    int nodeLength = 0;
    while ( frontNode != nullptr ){
        if ( front >= index ){
            tail++;
            tailNode = tailNode -> next;
        }
        // 获取链表长度
        nodeLength++;
        front++;
        frontNode = frontNode -> next;
    }

    // 判断index是否超出链表长度
    if ( nodeLength > index ){
        return tailNode;
    }else{
        return nullptr;
    }
}

// func 2
ListNode * findEndOfNode2(ListNode * head, int index ){
    if ( head ==  nullptr || index <= 0 ){
        return nullptr;
    }

    // 
    ListNode * frontNode = head;
    for ( int i=0; i<index; i++ ){
        if ( frontNode -> next != nullptr ){
            frontNode = frontNode -> next;
        }else {
            // 参数下标超出链表长度
            return nullptr;
        }
    }

    ListNode * tailNode = head;
    while ( frontNode != nullptr ){
        frontNode = frontNode -> next;
        tailNode = tailNode -> next;
    }

    return tailNode;
}

int main(void){
    int data[] = {1,2,3,4,5,6,7,8,9,0};
    ListNode * head = createNode(data, sizeof(data)/sizeof(int));
    ListNode * node = findEndOfNode2(head, 1);
    if ( node == nullptr ){
	    cout << "input param is invaild" << endl;
    }else{
        cout << node->value << endl;
    }    
    return 0;
}